|
In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair of ''a'', ''b'', and ''c''. The concept of median graphs has long been studied, for instance by or (more explicitly) by , but the first paper to call them "median graphs" appears to be . As Chung, Graham, and Saks write, "median graphs arise naturally in the study of ordered sets and discrete distributive lattices, and have an extensive literature".〔.〕 In phylogenetics, the Buneman graph representing all maximum parsimony evolutionary trees is a median graph.〔; ; .〕 Median graphs also arise in social choice theory: if a set of alternatives has the structure of a median graph, it is possible to derive in an unambiguous way a majority preference among them.〔; .〕 Additional surveys of median graphs are given by , , and . ==Examples== Every tree is a median graph.〔, Proposition 1.26, p. 24.〕 To see this, observe that in a tree, the union of the three shortest paths between pairs of the three vertices ''a'', ''b'', and ''c'' is either itself a path, or a subtree formed by three paths meeting at a single central node with degree three. If the union of the three paths is itself a path, the median ''m''(''a'',''b'',''c'') is equal to one of ''a'', ''b'', or ''c'', whichever of these three vertices is between the other two in the path. If the subtree formed by the union of the three paths is not a path, the median of the three vertices is the central degree-three node of the subtree. Additional examples of median graphs are provided by the grid graphs. In a grid graph, the coordinates of the median ''m''(''a'',''b'',''c'') can be found as the median of the coordinates of ''a'', ''b'', and ''c''. Conversely, it turns out that, in every median graph, one may label the vertices by points in an integer lattice in such a way that medians can be calculated coordinatewise in this way.〔This follows immediately from the characterization of median graphs as retracts of hypercubes, described below.〕 Squaregraphs, planar graphs in which all interior faces are quadrilaterals and all interior vertices have four or more incident edges, are another subclass of the median graphs.〔; ; .〕 A polyomino is a special case of a squaregraph and therefore also forms a median graph. The simplex graph κ(''G'') of an arbitrary undirected graph ''G'' has a node for every clique (complete subgraph) of ''G''; two nodes are linked by an edge if the corresponding cliques differ by one vertex. The median of a given triple of cliques may be formed by using the majority rule to determine which vertices of the cliques to include; the simplex graph is a median graph in which this rule determines the median of each triple of vertices. No cycle graph of length other than four can be a median graph, because every such cycle has three vertices ''a'', ''b'', and ''c'' such that the three shortest paths wrap all the way around the cycle without having a common intersection. For such a triple of vertices, there can be no median. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「median graph」の詳細全文を読む スポンサード リンク
|